letter = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:

        n = len(digits)
        if n == 0:
            return []

        ans = []
        path = [''] * n
        def dfs(v):
            if v == n:
                ans.append(''.join(path))
                return

            for c in letter[int(digits[v])]:
                path[v] = c
                dfs(v+1)

        dfs(0)
        return ans